/**
 * 给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。
 * 若可行，输出任意可行的结果。若不可行，返回空字符串。
 * @example 
 *  S = "aab"
 * ==> "aba"
 * 
 *  思路：
 *      1.初始化长度为26的桶
 *        遍历S字符串，按照字母扔进每个桶里，统计每个字母出现的次数
 *          注意字母转换为对应的unicode 编码
 *          如 a=> 0 b=>1 c=>2
 *      2.遍历桶得到次数最多的字母。记录桶的下标即字母
 *      3.遍历每个桶，将除去最大元素的桶的数全部取出来扔进数组temp里
 *          如 S= aaaabbbc
 *          那么 temp = [b,b,b,c]
 *      4.准备最大元素数组，和非最大元素数组，
 *        最大元素数组需要被非最大元素数组隔开。
 *      num = [a,a,a,a]
 *      temp= [b,b,b,c,c]
 * 
 *      5.遍历两个数组，开始进行交替插入。
 *        满足情况的优先条件：
 *          先满足 num被隔离开。
 *              即先用temp的数，隔一个插入一个数据
 *          当num被插入完并且temp还没被用完时，
 *          开始第二个插入满足：
 *              a,b,a,b,a   bcc
 *              if result[len-1]不能与temp[i] 那么直接插入到尾部
 *              如果等于，那么在result里找到 左邻右舍都不能与temp[i]的元素，
 *                  交换 temp[i],j
 * 
 *      思维突破点：
 *      1.知道求出最大连续数，如果不能满足最大连续数.len-1 < 其他数之和，
 *          那么肯定不能间接插入
 *      2.知道最大连续数组 [a,a,a,a] 和非最大数[b,b,b,c]
 *          求两个数组的间接插入
 *      ===》 试了很多方案，最后还是自己思路理清楚了，抽丝剥茧，
 *             化繁为简兼顾各个情况考虑周全了再写代码的栗子过了
 *          写代码果然是最后一步 啊，思考好了再出发
 *          还有，一道题有思路但是始终没过的时候是最好也是最坏得时候，得沉住气。
 *          想出来了很自豪
 *      
 *          和做数学题一样，平时的积累的思维、素养在真正临场发挥用的时候，都是习惯约束你，
 *          根本就没有时间思考太多代码优化的事情，只有做完了之后慢慢优化，
 *          所以平时一定要注重代码质量和编码速度，临场发挥的时候才能快准狠
 *  反思：
 *      1.为了达到关键步骤num 和temp相比那里，前戏太多
 *          可以不用字母转换为数字。
 *          使用hash = {} 标识，以每个字母做为下标
 *      
 */




var reorganizeString = function (S) {
    // 遍历S 将S里的每个字母扔进桶
    let bucket = new Array(26).fill(0); //记录26个字母出现频率
    for (let i = 0; i < S.length; i++) {
        let index = S.charCodeAt(i) - 97;
        bucket[index] = (bucket[index] || 0) + 1;
    }
    // 遍历桶得到含元素最多的桶的下标
    let maxIndex = 0;
    for (let i = 0; i < 26; i++) {
        maxIndex = bucket[maxIndex] > bucket[i] ? maxIndex : i;
    }
    // 统计非最大元素的其他有数的桶的个数
    let minCount = bucket[maxIndex] - 1; //填充字符需要的最少其他字符
    let temp = [];
    for (let i = 0; i < 26; i++) {
        while (bucket[i]--&&i !== maxIndex) {
            temp.push(i)
        }
    }
    // 间隔输出字符
    if (temp.length < minCount) {
        return "";
    }
    // 如果满足条件 bb 插入frs  // bbb 插入 aaacc
    let num = new Array(minCount+1).fill(maxIndex);
    
    let 
        p1 = 0,
        p2 = 0,
        result = [],
        numLen = num.length;
    while(p1<2*numLen-1&&p2<=temp.length){
        result[p1++]= p1%2?maxIndex:temp[p2++];
    }
    // 最多元素确认被分割之后
    while(p1<S.length){
        // 插入未相同的情况
        result[p1]=temp[p2];
        
        if(result[p1-1]===temp[p2]){
            for(let i=0;i<result.length;i++){
                if(result[i]!==temp[p2]&&result[i+2]&&result[i+2]!==temp[p2]){
                    swap(result,p1,i)
                    break;
                }
            }
        }
        p1++;
        p2++;
    }
    // 将数字转为字符，数组转为字符串
    for(let i=0;i<result.length;i++){
        result[i] = String.fromCharCode(result[i]+97);
    }
    return result.join("");
};

function swap(arr,i,j){
    [arr[i],arr[j]]  = [arr[j],arr[i]];
}

let res = reorganizeString("gpneqthatplqrofqgwwfmhzxjddhyupnluzkkysofgqawjyrwhfgdpkhiqgkpupgdeonipvptkfqluytogoljiaexrnxckeofqojltdjuujcnjdjohqbrzzzznymyrbbcjjmacdqyhpwtcmmlpjbqictcvjgswqyqcjcribfmyajsodsqicwallszoqkxjsoskxxstdeavavnqnrjelsxxlermaxmlgqaaeuvneovumneazaegtlztlxhihpqbajjwjujyorhldxxbdocklrklgvnoubegjrfrscigsemporrjkiyncugkksedfpuiqzbmwdaagqlxivxawccavcrtelscbewrqaxvhknxpyzdzjuhvoizxkcxuxllbkyyygtqdngpffvdvtivnbnlsurzroxyxcevsojbhjhujqxenhlvlgzcsibcxwomfpyevumljanfpjpyhsqxxnaewknpnuhpeffdvtyjqvvyzjeoctivqwann")
console.log(res)